#pragma once

#include <deque>
#include <functional>

namespace mdtx::online::container
{

    template <class T, class C = std::less<T>, class Allocator = std::allocator<T>>
    class sdeque : public std::deque<T, Allocator>
    {
    private:
        using base = std::deque<T, Allocator>;

    public:
        using typename base::value_type;
        using value_compare = C;
        using typename base::size_type;
        using typename base::difference_type;
        using typename base::const_iterator;
        using typename base::const_reference;

    public:
        // Lookup

        difference_type count(value_type const &v) const
        {
            const_iterator it0 = std::lower_bound(base::cbegin(), base::cend(), v, value_compare{});
            if (it0 == base::cend())
            {
                return 0;
            }
            else
            {
                const_iterator it1 = std::lower_bound(it0, base::cend(), v, value_compare{});
                return std::distance(it0, it1);
            }
        }

        const_iterator find(value_type const &v) const
        {
            const_iterator it = std::lower_bound(base::cbegin(), base::cend(), v, value_compare{});
            if (it != base::cend() && !value_compare{}(v, *it))
            {
                return it;
            }
            else
            {
                return base::cend();
            }
        }

        const_iterator lower_bound(value_type const &v) const
        {
            return std::lower_bound(base::cbegin(), base::cend(), v, value_compare{});
        }

        const_iterator upper_bound(value_type const &v) const
        {
            return std::upper_bound(base::cbegin(), base::cend(), v, value_compare{});
        }

        std::pair<const_iterator, const_iterator> equal_range(value_type const &v) const
        {
            return std::equal_range(base::cbegin(), base::cend(), v, value_compare{});
        }

        const_reference at(size_type pos) const
        {
            return base::at(pos);
        }

        const_reference operator[](size_type pos) const
        {
            return base::operator[](pos);
        }

        const_reference front() const
        {
            return base::front();
        }

        const_reference back() const
        {
            return base::back();
        }

        // Iterator

        const_iterator begin() const
        {
            return base::cbegin();
        }

        const_iterator end() const
        {
            return base::cend();
        }

        const_iterator rbegin() const
        {
            return base::crbegin();
        }

        const_iterator rend() const
        {
            return base::crend();
        }

        // Modifier

        const_iterator insert(value_type const &v)
        {
            auto it = std::lower_bound(base::begin(), base::end(), v, value_compare{});
            return base::insert(it, v);
        }

        const_iterator insert(value_type &&v)
        {
            auto it = std::lower_bound(base::begin(), base::end(), v, value_compare{});
            return base::insert(it, std::move(v));
        }

        void push_front(value_type const &v)
        {
            if (base::empty() || value_compare{}(v, base::front()))
            {
                base::push_front(v);
            }
            else
            {
                insert(v);
            }
        }

        void push_front(value_type &&v)
        {
            if (base::empty() || value_compare{}(v, base::front()))
            {
                base::push_front(std::move(v));
            }
            else
            {
                insert(std::move(v));
            }
        }

        void push_back(value_type const &v)
        {
            if (base::empty() || value_compare{}(base::back(), v))
            {
                base::push_back(v);
            }
            else
            {
                insert(v);
            }
        }

        void push_back(value_type &&v)
        {
            if (base::empty() || value_compare{}(base::back(), v))
            {
                base::push_back(std::move(v));
            }
            else
            {
                insert(std::move(v));
            }
        }

        void erase(value_type const &v)
        {
            auto it = std::lower_bound(base::begin(), base::end(), v, value_compare{});
            if (it != base::end() && !value_compare{}(v, *it))
            {
                base::erase(it);
            }
        }

        void erase_rank(size_type rank)
        {
            base::erase(base::begin() + rank);
        }

        template <typename Container>
        void merge(Container const &other)
        {
            for (auto const &node : other)
            {
                insert(node);
            }
        }

        using base::pop_back;
        using base::pop_front;

    private:
        using base::assign;
        using base::emplace;
        using base::emplace_back;
        using base::emplace_front;
        using base::resize;
    };

}
